Crate sanakirja_core

This crate defines tools to implement datastructures that can live in main memory or on-disk, meaning that their natural habitat is memory-mapped files, but if that environment is threatened, they might seek refuge in lower-level environments.

One core building block of this library is the notion of virtual memory pages, which are allocated and freed by an externally-provided allocator (see how the sanakirja crate does this). The particular implementation used here is meant to allow a transactional system with readers reading the structures concurrently with one writer at a time.

At the moment, only B trees are implemented, as well as the following general traits:

• LoadPage is a trait used to get a pointer to a page. In the most basic version, this may just return a pointer to the file, offset by the requested offset. In more sophisticated versions, this can be used to encrypt and compress pages.
• AllocPage allocates and frees pages, because as datastructures need to be persisted on disk, we can’t rely on Rust’s memory management to do it for us. Users of this crate don’t have to worry about this though.

Moreover, two other traits can be used to store things on pages: Storable is a simple trait that all Sized + Ord types without references can readily implement (the direct_repr! macro does that). For types containing references to pages allocated in the database, the comparison function can be customised. Moreover, these types must supply an iterator over these references, in order for reference-counting to work properly when the datastructures referencing these types are forked.

Dynamically-sized types, or types that need to be represented in a dynamically-sized way, can use the UnsizedStorable format.

Modules

• btree
  An implementation of B trees. The core operations on B trees (lookup, iterate, put and del) are generic in the actual implementation of nodes, via the BTreePage and BTreeMutPage. This allows for a simpler code for the high-level functions, as well as specialised, high-performance implementations for the nodes.

Macros

• direct_repr
  A macro to implement Storable on “plain” types, i.e. fixed-sized types that are repr(C) and don’t hold references.

Structs

• CowPage
  Representation of a mutable or shared page. This is an owned page (like Vec in Rust’s std), but we do not know whether we can mutate it or not.
• MutPage
  An owned page on which we can write. This is just a wrapper around CowPage to avoid checking the “dirty” bit at runtime.
• Page
  Representation of a borrowed, or immutable page, like a slice in Rust.
• Pages

Constants

• PAGE_SIZE
  There’s a hard-coded assumption that pages have 4K bytes. This is true for normal memory pages on almost all platforms.

Traits

• AllocPage
  Trait for allocating and freeing pages.
• LoadPage
  Trait for loading a page.
• Storable
  Types that can be stored on disk. This trait may be used in conjunction with Sized in order to determine the on-disk size, or with UnsizedStorable when special arrangements are needed.
• UnsizedStorable
  Types that can be stored on disk.

Functions

• clear_dirty

Unions

• Slice